Jump instructions are commonly included in the instruction set architecture of a digital processor. During sequential program execution, a processor fetches instructions from sequential memory addresses. A jump instruction is used to switch program execution from a first instruction sequence to a second instruction sequence and, either directly or indirectly, specifies a target address. The target address contains the first instruction of the second instruction sequence. When the processor fetches the jump instruction from memory, it jumps to the target address and begins execution of the second instruction sequence.
A program may include multiple jump instructions, each with a different target address. The jump instruction may be used, for example, to execute different subroutines. A jump instruction may be conditional or unconditional. A conditional jump instruction is commonly known as a branch instruction.
Current processors typically use pipelined architectures. Such processors include multiple pipeline stages to achieve high speed operation. Each pipeline stage performs one of the functions involved in instruction execution, such as instruction fetch, instruction decode, data address generation, computation, and the like. Program instructions advance through the pipeline stages on consecutive clock cycles, and several instructions may be in various stages of completion at the same time. Ideally, a pipelined processor can complete execution of one instruction per clock cycle. Performance can be enhanced by providing a large number of pipeline stages. The number of pipeline stages in a processor is commonly referred to as “pipeline depth.”
Notwithstanding the enhanced performance provided by pipelined architectures, certain program conditions may degrade performance. An example of such a program condition is a jump instruction. Jump instructions are common in most computer programs, including for example, digital signal processor applications and microcontroller applications. When a jump instruction advances through a pipelined processor and branch prediction is not utilized, sequential instructions follow the jump instruction in the pipeline. When the jump instruction is commits at the end of the pipeline, the pipeline must be cleared by aborting all instructions currently in the pipeline and re-executing instructions beginning at the target address of the jump instruction. The performance penalty increases with the pipeline depth. For deeply pipelined architectures and programs having frequent jump instructions, the performance penalty can be severe.
Branch prediction techniques are known in the art. In a typical branch predictor, a branch cache memory contains the addresses of branch and jump instructions, and corresponding prediction information. When a jump instruction is fetched by the program sequencer, the branch predictor detects the jump instruction based on its memory address. The prediction information contained in the branch cache memory permits the processor to jump to the target address without flushing of the pipeline.
Prior art branch predictors have had limited impact on performance. Accordingly, there is a need for improved methods and apparatus for performing jump operations in a digital processor.